package demo7;

import java.util.Arrays;

/**
 * 数组的堆排序
 */
public class Main2 {
    public static void main(String[] args) {
        int[] arr = {5,2,8,6,1,9,10,45,12};
        heapSort(arr,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr,int lastIndex){

        // 递归终止条件
        if(lastIndex < 1) return;

        // 建大顶堆堆,从最后一个非叶子节点开始向前调整
        for (int i = (lastIndex-1)/2; i >= 0 ; i--) {
            buildHeap(arr,i,lastIndex);
        }

        // 调整,把第一个位置的元素和最后一个位置的元素互换
        swap(arr,0,lastIndex);

        // 递归
        heapSort(arr,lastIndex-1);

    }

    public static void buildHeap(int[] arr,int i,int lastIndex){

        int left = 2*i + 1;  // 左子节点
        int right = 2*i + 2;  // 右子节点
        if(left <= lastIndex && arr[i] < arr[left]){
            swap(arr,i,left);
        }
        if(right <= lastIndex && arr[i] < arr[right]){
            swap(arr,i,right);
        }
    }

    public static void swap(int[] arr, int i, int j){
        // 交换数组i和j位置的元素
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
